package offer;

public class offerII_0009 {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int len=nums.length;
        int left=0;
        int right=0;
        int num=0;
        long mul=1;
        for(int i=0;i<len;++i){
            left=i;
            right=i;
            mul*=nums[left];
            if(mul<k) num++;
            else {mul=1;continue;}
            left--;
            right++;
            while(left>=0&&right<len){
                long tem=mul;
                mul*=nums[right];
                mul*=nums[left];
                if(tem>mul) break;
                left--;right++;
                if(mul<k) num++;
                else break;
            }
            mul=1;
        }
        for(int i=0;i<len-1;++i){
            left=i;
            right=i+1;
            mul*=nums[left];
            mul*=nums[right];
            if(mul<k) num++;
            else {mul=1;continue;}
            left--;
            right++;
            while(left>=0&&right<len){
                long tem=mul;
                mul*=nums[right];
                mul*=nums[left];
                if(tem>mul) break;
                left--;right++;
                if(mul<k) num++;
                else break;
            }
            mul=1;
        }
        return num;
    }
}
